#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>

    //class Partition {
    //public:
    //    struct ListNode* head1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    //    struct ListNode* head2 = (struct ListNode*)malloc(sizeof(struct ListNode));

    //    ListNode* partition(ListNode* pHead, int x) {
    //        // write code here
    //        struct ListNode* ret1 = head1;
    //        struct ListNode* ret2 = head2;
    //        while (pHead)
    //        {
    //            if (pHead->val < x)
    //            {
    //                ret1->next = pHead;
    //                ret1 = ret1->next;
    //            }
    //            else {
    //                ret2->next = pHead;
    //                ret2 = ret2->next;
    //            }
    //            pHead = pHead->next;
    //        }
    //        ret1->next = head2->next;
    //        ret2->next = NULL;
    //        return head1->next;
    //    }
    //};


//class PalindromeList {
//public:
//    struct ListNode* MidNode(struct ListNode* A)
//    {
//        struct ListNode* fast = A;
//        struct ListNode* slow = A;
//        int x = 0;
//        while (fast)
//        {
//            fast = fast->next;
//            x++;
//            if (x % 2 == 0)
//            {
//                slow = slow->next;
//            }
//        }
//        return slow;
//    }
//
//    struct ListNode* InvertNode(struct ListNode* A)
//    {
//        struct ListNode* p1 = NULL;
//        struct ListNode* p2 = A;
//        struct ListNode* p3 = A;
//        while (p3)
//        {
//            p3 = p3->next;
//            p2->next = p1;
//            p1 = p2;
//            p2 = p3;
//        }
//        return p1;
//    }
//
//    bool chkPalindrome(ListNode* A) {
//        // write code here
//        //ListNode* p = A;
//        struct ListNode* mid = MidNode(A);
//        struct ListNode* invert = InvertNode(mid);
//        while (A != mid)
//        {
//            if (A->val != invert->val)
//            {
//                return false;
//            }
//            A = A->next;
//            invert = invert->next;
//        }
//        return true;
//    }
//};


//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    int sumA = 0;
//    int sumB = 0;
//    struct ListNode* pA = headA;
//    struct ListNode* pB = headB;
//    while (pA)
//    {
//        sumA++;
//        pA = pA->next;
//    }
//    while (pB)
//    {
//        sumB++;
//        pB = pB->next;
//    }
//
//    if (sumA > sumB)
//    {
//        int x = sumA - sumB;
//        while (x--)
//        {
//            headA = headA->next;
//        }
//        while (headA && headB)
//        {
//            if (headA == headB)
//            {
//                return headA;
//            }
//            headA = headA->next;
//            headB = headB->next;
//        }
//        return NULL;
//    }
//    else
//    {
//        int j = sumB - sumA;
//        while (j--)
//        {
//            headB = headB->next;
//        }
//        while (headA && headB)
//        {
//            if (headA == headB)
//            {
//                return headA;
//            }
//            headA = headA->next;
//            headB = headB->next;
//        }
//        return NULL;
//    }
//}



//bool hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//    int x = 0;
//    while (fast)
//    {
//        fast = fast->next;
//        x++;
//        if (x % 2 == 0)
//        {
//            slow = slow->next;
//        }
//        if (fast == slow)
//        {
//            return true;
//        }
//    }
//    return false;
//}


//struct ListNode* hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//    int x = 0;
//    while (fast)
//    {
//        fast = fast->next;
//        x++;
//        if (x % 2 == 0)
//        {
//            slow = slow->next;
//            if (fast == slow)
//            {
//                return fast;
//            }
//        }
//    }
//    return NULL;
//}
//
//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* p = hasCycle(head);
//    if (p != NULL)
//    {
//        while (1)
//        {
//            if (head == p)
//            {
//                return p;
//            }
//            head = head->next;
//            p = p->next;
//        }
//    }
//    return NULL;
//}

//struct Node* copyRandomList(struct Node* head) {
//    if (head == NULL)
//    {
//        return NULL;
//    }
//
//    struct Node* p = head;
//    while (p)
//    {
//        struct Node* new = (struct Node*)malloc(sizeof(struct Node));
//        new->val = p->val;
//        new->random = NULL;
//        new->next = p->next;
//        p->next = new;
//        p = new->next;
//    }
//    struct Node* p1 = head;
//    struct Node* p2 = head;
//    while (p1)
//    {
//        p2 = p1->next;
//        if (p1->random == NULL)
//        {
//            p2->random = NULL;
//        }
//        else
//        {
//            p2->random = p1->random->next;
//        }
//        p1 = p2->next;
//    }
//    p1 = head;
//    p2 = head->next;
//    p = head->next;
//    while (p2 != NULL)
//    {
//        p1->next = p2->next;
//        p1 = p2;
//        p2 = p2->next;
//    }
//    return p;
//}